package problem204_Count_Primes;

/**
 * 将所有合数标记为true
 * @author I321035
 *
 */
public class Solution {
	public int countPrimes(int n) {
		boolean[] isComposite=new boolean[n];
		for(int i=2;i*i<n;i++){
			if(!isComposite[i]){
				for(int j=i;j*i<n;j++){
					isComposite[j*i]=true;
				}
			}
		}
		int result=0;
		for(int i=2;i<n;i++){
			if(!isComposite[i])
				result++;
		}
		return result;
    }
}
